/*
 * @lc app=leetcode.cn id=433 lang=golang
 *
 * [433] 最小基因变化
 */

// 2. 这个history存放每次变换的历史记录，变换之后的必须不包含在history里面，不然就无限递归了
// @lc code=start
func minMutation(startGene string, endGene string, bank []string) int {
	ans := math.MaxInt64
	var mutation func(startGene string, history []string, count int)
	mutation = func(startGene string, history []string, count int) {
		if startGene == endGene {
			ans = min(ans, count)
			return
		}

		for i := 0; i < len(startGene); i++ {
			for _, v := range []byte{'A', 'C', 'G', 'T'} {
				if startGene[i] == v {
					continue
				}
				bytes := []byte(startGene)
				bytes[i] = v
				temp := string(bytes)
				if contain(temp, bank) && !contain(temp, history) {
					mutation(temp, append(history, temp), count+1)
				}
			}
		}
	}
	mutation(startGene, []string{}, 0)

	if ans == math.MaxInt64 {
		return -1
	}

	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func contain(value string, bank []string) bool {
	for i := 0; i < len(bank); i++ {
		if bank[i] == value {
			return true
		}
	}
	return false
}

// @lc code=end

// 1. 这个思路不行，不能反着推，因为start可以变得千奇百怪（符合bank），再变回来
// @lc code=start
func minMutation(startGene string, endGene string, bank []string) int {
	ans := -1
	var mutation func(startGene string, count int)
	mutation = func(startGene string, count int) {
		if startGene == endGene {
			ans = count
			return
		}

		pos := 0
		for pos < len(endGene) {
			for ; pos < len(endGene) && startGene[pos] == endGene[pos]; pos++ {
			}

			if pos == len(endGene) {
				return
			}

			bytes := []byte(startGene)
			bytes[pos] = endGene[pos]
			temp := string(bytes)

			pos++
			if contain(temp, bank) {
				mutation(temp, count+1)
			}
		}
	}
	mutation(startGene, 0)
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func contain(value string, bank []string) bool {
	for i := 0; i < len(bank); i++ {
		if bank[i] == value {
			return true
		}
	}
	return false
}

// @lc code=end

